package com.example.demo.algorithm.graph;

import com.example.demo.algorithm.linear.Stack;

/**
 * @Author: xiatian
 * @CreateTime: 2022/2/6 1:55 下午
 * @Description: 深度优先搜索路径
 */
public class DepthFirstPaths {
    //索引代表顶点，值标识当前顶点是否已经被搜索
    private boolean[] marked;
    //起点
    private int s;
    //索引代表顶点，值表示从起点s到当前顶点路径上的最后一个顶点
    private int[] edgeTo;

    //构造深度优先搜索对象，使用深度优先搜索找到g图中起点为s的所有路径
    public DepthFirstPaths(Graph g, int s) {
        //初始化marked数组
        this.marked = new boolean[g.V()];
        //初始化起点
        this.s = s;
        //初始化edgeTo数组
        this.edgeTo = new int[g.V()];
        dfs(g, s);
    }

    /**
     * 使用深度优先搜索找出g图中v顶点的所有相邻顶点
     *
     * @param g
     * @param v
     */
    private void dfs(Graph g, int v) {
        //把v标识为已搜索
        marked[v] = true;
        //遍历顶点v的领接表，拿到每一个相邻的顶点，继续递归搜索
        for (Integer w : g.adj(v)) {
            //如果顶点w没有被搜索，则继续递归搜索
            if (!marked[w]) {
                //到达顶点w路径上的最后一个顶点是v
                edgeTo[w] = v;
                dfs(g, w);
            }
        }
    }

    /**
     * 判断w顶点与s顶点是否存在路径(相通的就有路径)
     *
     * @param v
     * @return
     */
    public boolean hasPathTo(int v) {
        return marked[v];
    }

    /**
     * 找出从起点s到顶点v的路径（就是该路径经过的顶点）
     *
     * @param v
     * @return
     */
    public Stack<Integer> pathTo(int v) {
        //首先判断是否相通
        if (!hasPathTo(v)) {
            return null;
        }
        //创建栈对象，保存路径中所有顶点
        Stack<Integer> path = new Stack<>();
        //通过循环，从顶点v开始一直往前找到找到起点为止
        for (int x = v; x != s; x = edgeTo[x]) {
            path.push(x);
        }
        //把起点s放到栈中
        path.push(s);
        return path;
    }

}
